<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 图的邻接矩阵
        var graph = [[0, 2, 4, 0, 0, 0],
                    [0, 0, 3, 4, 2, 0],
                    [0, 0, 0, 0, 3, 0],
                    [0, 0, 0, 0, 0, 2],
                    [0, 0, 0, 3, 0, 2],
                    [0, 0, 0, 0, 0, 0]];

        // 无穷大常量
        const INF = Number.MAX_SAFE_INTEGER;

        /**
         * 计算路径数组中源点到未被访问顶点的最短路径
         * @param {*} dist     路径距离数组
         * @param {*} visited  访问记录数组
         */
        const minDistance = (dist, visited) => {
            let min = INF;
            let minIndex = -1;
            for (let v = 0; v < dist.length; v++) {
                if (visited[v] === false && dist[v] <= min) {
                    min = dist[v];
                    minIndex = v;
                }
            }
            return minIndex;
        };
        
        /**
         * Dijkstra 算法求最短路径
         * @param {*} graph     图的邻接矩阵
         * @param {*} src       起始顶点的索引（源点）
         */
        const dijkstra = (graph, startIndex) => {
            // 存储源点到各顶点路径距离的数组
            const dist = [];
            // 判断该顶点是否被访问过
            const visited = [];
            // 解构，获取顶点数量
            const { length } = graph;
            for(let i = 0; i < length; i++){
                // 将 dist 的每个元素都初始化为无穷大
                dist[i] = INF;
                // 将 visited 的每个元素初始化为 false 未访问状态
                visited[i] = false;
            }
            // 将源顶点到自身的距离设为0
            dist[startIndex] = 0;
            // 遍历每个顶点
            for (let i = 0; i < length; i++) {
                // 从尚未访问的顶点中选出距离最近的顶点
                const u = minDistance(dist, visited);
                // 把选出的顶点标为 visited，以免重复计算
                visited[u] = true;
                // 遍历 u 的邻接顶点
                for(let v = 0; v < length; v++){
                    // 若 u 到邻接节点 v 的距离加上 u 到源点的距离小于 路径数组中 v 到源点的距离，即可更新为最短路径
                    if(!visited[v] &&
                        graph[u][v] !== 0 &&
                        dist[u] !== INF &&
                        dist[u] + graph[u][v] < dist[v])
                    {
                        // 更新最短路径的值
                        dist[v] = dist [u] + graph[u][v];
                    }
                }
            }
            return dist;
        }
        console.log(dijkstra(graph, 0));
    </script>
</body>
</html>